//===--------------- Permutations.swift - Swift Permutations --------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2019 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

// Copied from StdlibCoreExtras.swift in StdlibUnittest.

enum FormNextPermutationResult {
  case success
  case formedFirstPermutation
}

extension MutableCollection
  where
  Self : BidirectionalCollection,
  Iterator.Element : Comparable
{
  mutating func _reverseSubrange(_ subrange: Range<Index>) {
    if subrange.isEmpty { return }
    var f = subrange.lowerBound
    var l = index(before: subrange.upperBound)
    while f < l {
      swapAt(f, l)
      formIndex(after: &f)
      formIndex(before: &l)
    }
  }

  mutating func formNextPermutation() -> FormNextPermutationResult {
    if isEmpty {
      // There are 0 elements, only one permutation is possible.
      return .formedFirstPermutation
    }

    do {
      var i = startIndex
      formIndex(after: &i)
      if i == endIndex {
        // There is only element, only one permutation is possible.
        return .formedFirstPermutation
      }
    }

    var i = endIndex
    formIndex(before: &i)
    var beforeI = i
    formIndex(before: &beforeI)
    var elementAtI = self[i]
    var elementAtBeforeI = self[beforeI]
    while true {
      if elementAtBeforeI < elementAtI {
        // Elements at `i..<endIndex` are in non-increasing order.  To form the
        // next permutation in lexicographical order we need to replace
        // `self[i-1]` with the next larger element found in the tail, and
        // reverse the tail.  For example:
        //
        //       i-1 i        endIndex
        //        V  V           V
        //     6  2  8  7  4  1 [ ]  // Input.
        //     6 (4) 8  7 (2) 1 [ ]  // Exchanged self[i-1] with the
        //        ^--------^         // next larger element
        //                           // from the tail.
        //     6  4 (1)(2)(7)(8)[ ]  // Reversed the tail.
        //           <-------->
        var j = endIndex
        repeat {
          formIndex(before: &j)
        } while !(elementAtBeforeI < self[j])
        swapAt(beforeI, j)
        _reverseSubrange(i..<endIndex)
        return .success
      }
      if beforeI == startIndex {
        // All elements are in non-increasing order.  Reverse to form the first
        // permutation, where all elements are sorted (in non-increasing order).
        reverse()
        return .formedFirstPermutation
      }
      i = beforeI
      formIndex(before: &beforeI)
      elementAtI = elementAtBeforeI
      elementAtBeforeI = self[beforeI]
    }
  }
}

/// Generate all permutations.
public func forAllPermutations(_ size: Int, _ body: ([Int]) -> Void) {
  var data = Array(0..<size)
  repeat {
    body(data)
  } while data.formNextPermutation() != .formedFirstPermutation
}
